/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 143. 重排链表
 * <a href="https://leetcode.cn/problems/reorder-list/">...</a>
 * User: DELL
 * Date: 2023-10-09
 * Time: 23:10
 */
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    /**
     * 解题思路:
     * 首先应该将该题目分为几个小步骤,具体的分布如下:
     * 1. 找到链表的中间节点
     * 2. 将链表截断并且逆序后半部分链表
     * 3. 将两个链表交叉合并
     * 根据以上三个步骤,依次完成即可.
     * 其中要注意的就是中间节点是偶数情况下要找偏左的节点,
     * 之后要将该节点的 next 域置为空
     *
     * @param head
     */
    public void reorderList(ListNode head) {
        // 判空处理
        if (head == null) {
            return;
        }
        // 先找到链表的中间结点(中间偏左)
        ListNode mid = midNode(head);
        // 逆序后半链表
        ListNode temp = mid.next;
        mid.next = null;
        ListNode right = reverse(temp);
        // 将两段链表交叉合并
        ListNode left = head;
        temp = new ListNode();
        while (right != null) {
            // 拼接左边节点
            temp.next = left;
            left = left.next;
            temp = temp.next;
            temp.next = right;
            right = right.next;
            temp = temp.next;
        }
        if (left != null) {
            temp.next = left;
        }
        return;
    }

    private ListNode midNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
